/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.greedy;

/**
 * <p>
 * 蛙跳，能够到达终点求出 最少跳数
 * 
 * Given array A = [2,3,1,1,4]
 * The minimum number of jumps to reach the last index is 2
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月31日
 */
public class JumpGameII {

    public int jump(int[] nums) {
        int result = 0;
        int last = 0;
        int curr = 0;
        for(int i=0;i<nums.length;i++){
            if(i>last){
                //如果当前指针越过上一轮最远目的地，更新上一轮指针，实施一跳
                last = curr;
                result++;
            }
            //保存本轮的最远目的地址
            curr = Math.max(curr, i+nums[i]);
        }
        return result;
    }
}
